package com.nanbei.redblack;

import com.nanbei.tree.BSTNode;
import org.junit.Test;

/**
 * @ClassDescription: 红黑树
 * @JdkVersion: 17
 * @Author: BaoShan.Li
 * @Created: 2024/6/11 15:17
 */
public class RedBlackTreeTest {

    @Test
    public void testPut1(){
        RedBlackTree redBlackTree = new RedBlackTree();
        // 添加的节点为根节点
        redBlackTree.put(30,30);
        // 插入节点的父亲若为黑色，树的红黑性质不变，无需调整
        redBlackTree.put(25,25);

        // 当叔叔节点为黑色时(如果叔叔节点为null,null也默认为黑色节点)  LL 不平衡
        redBlackTree.put(20,20);
        // 当叔叔节点为红色时 : 将父节点和叔叔节点调为黑色，将爷爷节点调为红色，在递归调用爷爷节点
        redBlackTree.put(15,15);

    }

    @Test
    public void testPut2(){
        RedBlackTree redBlackTree = new RedBlackTree();
        // 添加的节点为根节点
        redBlackTree.put(30,30);
        // 插入节点的父亲若为黑色，树的红黑性质不变，无需调整
        redBlackTree.put(20,20);

        // 当叔叔节点为黑色时(如果叔叔节点为null,null也默认为黑色节点) LR不平衡
        redBlackTree.put(25,25);

    }

    @Test
    public void testPut3(){
        RedBlackTree redBlackTree = new RedBlackTree();
        // 添加的节点为根节点
        redBlackTree.put(10,10);
        // 插入节点的父亲若为黑色，树的红黑性质不变，无需调整
        redBlackTree.put(20,20);

        // 当叔叔节点为黑色时(如果叔叔节点为null,null也默认为黑色节点) RR不平衡
        redBlackTree.put(25,25);

    }

    @Test
    public void testPut4(){
        RedBlackTree redBlackTree = new RedBlackTree();
        // 添加的节点为根节点
        redBlackTree.put(10,10);
        // 插入节点的父亲若为黑色，树的红黑性质不变，无需调整
        redBlackTree.put(20,20);

        // 当叔叔节点为黑色时(如果叔叔节点为null,null也默认为黑色节点) RL不平衡
        redBlackTree.put(15,15);

    }


    @Test
    public void testRemove(){
        RedBlackNode node20 = new RedBlackNode(20, 20);
        RedBlackNode node10 = new RedBlackNode(10, 10);
        RedBlackNode node1 = new RedBlackNode(1, 1);
        RedBlackNode node15 = new RedBlackNode(15, 15);
        RedBlackNode node30 = new RedBlackNode(30, 30);
        RedBlackNode node25 = new RedBlackNode(25, 25);
        RedBlackNode node35 = new RedBlackNode(35, 35);
        node20.color = node10.color = node30.color = Color.BLACK;
        node1.color =node15.color =node25.color =node35.color = Color.RED;

        node20.left = node10;
        node20.right = node30;
        node10.left = node1;
        node10.right = node15;
        node30.left = node25;
        node30.right = node35;

        node10.parent = node20;
        node30.parent = node20;
        node1.parent = node10;
        node15.parent = node10;
        node25.parent = node30;
        node35.parent = node30;

        RedBlackTree redBlackTree = new RedBlackTree(node20);
        redBlackTree.remove(10);


    }


    @Test
    public void testRemoveCase3_4(){
        RedBlackNode node6 = new RedBlackNode(6, 6);
        RedBlackNode node4 = new RedBlackNode(4, 4);
        RedBlackNode node8 = new RedBlackNode(8, 8);
        RedBlackNode node7 = new RedBlackNode(7, 7);
        RedBlackNode node9 = new RedBlackNode(9, 9);
        node4.color = node6.color = node7.color = node9.color =  Color.BLACK;
        node8.color  = Color.RED;

        node4.parent = node6;
        node8.parent = node6;
        node7.parent = node8;
        node9.parent = node8;

        node6.left = node4;
        node6.right = node8;
        node8.left = node7;
        node8.right = node9;



        RedBlackTree redBlackTree = new RedBlackTree(node6);
        redBlackTree.remove(4);


    }
}
